package main.leetcode.clockin.June;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 128. 最长连续序列
 *
 * <p>给定一个未排序的整数数组，找出最长连续序列的长度。
 *
 * <p>要求算法的时间复杂度为 O(n)。
 *
 * <p>示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
 */
public class day6 {
    public static void main(String[] args) {
        System.out.println(new day6().longestConsecutive(new int[] {100, 4, 200, 1, 3, 2}));
        System.out.println(new day6().longestConsecutive(new int[] {0, -1}));
        System.out.println(new day6().longestConsecutive(new int[] {1, 2, 0, 1}));
    }

    /** 暴力 O(nlogn) */
    public int longestConsecutive1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int pre = nums[0];
        int n = nums.length;
        int res = 1;
        int cur = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == pre + 1) {
                ++cur;
            } else if (nums[i] == pre) {
                continue;
            } else {
                res = Math.max(res, cur);
                cur = 1;
            }
            pre = nums[i];
        }
        res = Math.max(res, cur);
        return res;
    }

    /** SET O(n) */
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        int start, end;
        for (int num : nums) {
            if (set.remove(num)) {
                start = num;
                // 向左搜索
                while (set.remove(start - 1)) {
                    --start;
                }
                end = num;
                // 向右搜索
                while (set.remove(end + 1)) {
                    ++end;
                }
                res = Math.max(res, end - start + 1);
            }
        }
        return res;
    }
}
